#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include "euler.h"

BEGIN_PROBLEM(336, solve_problem_336)
	PROBLEM_TITLE("Maximix arrangements")
	PROBLEM_ANSWER("CAGBIHEFJDK")
	PROBLEM_DIFFICULTY(2)
	PROBLEM_FUN_LEVEL(3)
	PROBLEM_TIME_COMPLEXITY("N!")
	PROBLEM_SPACE_COMPLEXITY("(N-2)!")
	PROBLEM_KEYWORDS("combinatorics")
END_PROBLEM()

// Generate all maximix permutations of length N, start labelling at c.
// The generated permutations are not sorted.
static std::vector<std::string> generate_permutation(int N, char c)
{
	std::vector<std::string> perms;

	if (N < 2)
		return perms;

	// If there are two carriages, return BA.
	if (N == 2)
	{
		std::string p(2, 0);
		p[0] = c + 1;
		p[1] = c;
		perms.push_back(p);
		return perms;
	}

	// Generate all (N-1) maximix arrangements.
	std::vector<std::string> perms_1 = generate_permutation(N-1, c+1);
	perms.reserve(perms_1.size()*(N-2));

	// For each (N-1) sequence, insert A into any of the (N-2) slots.
	std::string p(N, 0);
	for (auto it = perms_1.cbegin(); it != perms_1.cend(); ++it)
	{
		const std::string &s = *it;
		for (int k = 1; k <= N - 2; k++)
		{
			p[N-1-k] = c;
			for (int j = 0; j < N-1-k; j++)
				p[j] = s[N-2-j];
			for (int j = 0; j < k; j++)
				p[N-k+j] = s[j];
			perms.push_back(p);
		}
	}

	return perms;
}

static void solve_problem_336()
{
#if 0
	const int N = 6; // DFAECB
	const int K = 10;
#else
	const int N = 11;
	const int K = 2011;
#endif

	bool verbose = false;
	std::vector<std::string> perms = generate_permutation(N, 'A');

	if (verbose)
	{
		std::sort(perms.begin(), perms.end());
		for (int i = 0; i < (int)perms.size(); i++)
			std::cout << "[" << (i+1) << "] " << perms[i] << std::endl;
	}
	else
	{
		std::nth_element(perms.begin(), perms.begin()+K-1, perms.end());
		std::cout << perms[K-1] << std::endl;
	}
}
